/*
 * File:   starosta.cpp
 * Author: Michal Zima
 *
 * Created on 17. kvďż˝ten 2009, 18:58
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include <time.h>
#include <unistd.h>
/*
 *       Deklarace struktur a promÄ›nnĂ˝ch
 */

typedef struct route
{
    int route_ID;
    char where_from;
    int where_from_ID;
    char where;
    int where_ID;
    int length;
    route* next_route;

};

typedef struct city
{
    int city_ID;
    char name;
    int coordinate_x;
    int coordinate_y;
    int distance;
    int close;
    city* next_city;
    route* route_in;
    route* route_out;
//    next_way* way; - něco, co by mělo uchovat cesty do mesta, aby se prochazely
};

typedef struct queue
{
    queue* next;
    queue* prev;
    int city_ID;
    int route_length;
    
};

queue* actual = new queue();

city* first_city = NULL;
city* g_c;

int g_city_ID = 0;
int g_route_ID = 0;
/*
 *Deklarace funkci..
*/

void err(int err_num) // controled
{
    printf("Nastala kriticka chyba, program bude ukoncen... Cislo chyby: %d\n",err_num);
    exit(-1);
}

void print() //controled
{
    printf("Vypis mest a cest: \n");
    city* c = first_city;
    route* r = new route();

    while (c != NULL)
    {
        printf("Mesto: '%c'(%d), souradnice_x: %d, souradnice_y: %d ma cesty: \n", c -> name, c -> city_ID ,c-> coordinate_x, c -> coordinate_y);
        r = c -> route_out;
        while (r != NULL)
        {
            printf("          cesta %d vede z %c(%d) do %c(%d) a je dlouha %d\n", r -> route_ID, r->where_from, r->where_from_ID, r->where, r ->where_ID, r ->length);
            r = r -> next_route;
        }
        c = c -> next_city;
    }
    printf("Konec vypisu mest a cest..\n");
}

void print_q() // controled
{
    queue* q = actual;
    printf("\nVypis fronty!\n");
    while(q != NULL)
    {
        printf("Fr: %d, pro m: %d, delka: %d, next: %d, prev: %d \n",(int)q, q->city_ID, q->route_length, (int)q->next, (int)q->prev);
        q = q -> next;
    }
    printf("Konec vypisu fronty!\n\n");
}

void print_usefull() // controled
{
    city* c = first_city;
    printf("\nVypis uzitecnych cest (ty ktere se nesmi opravovat): \n");
    while(c != NULL)
    {
        if (c->route_in != NULL)
        {
            printf("Cesta(%c) ID: %d, z '%c' do '%c' dlouha %d se nebude opravovat..\n", c->name, c->route_in->route_ID, c->route_in->where_from, c->route_in->where, c->route_in->length);
        }
        c = c -> next_city;
    }
    printf("Konec vypisu uzitecnych cest!\n\n");
}

void  create_city(char ID_city, int c_x, int c_y) // functional
{
    g_city_ID++;
    city* c = new city();
    if (g_city_ID == 1)
    {
        first_city = c;
        g_c = c;
    }
    else
    {
        g_c -> next_city = c;
        g_c = c;
    }

    c -> city_ID = g_city_ID;
    c -> coordinate_x = c_x;
    c -> coordinate_y = c_y;
    c -> distance = -1;
    c -> name = ID_city;
    c -> route_in = NULL;
    c -> next_city = NULL;
    c -> route_out = NULL;
    c -> close = 0;
 }

int find_city_ID(char name) //controled
{
    city* c = first_city;
    if (c == NULL) {err(5);}

    while(c->name != name)
    {
        if (c == NULL){err(5);}
        c = c -> next_city;
    }
    return(c -> city_ID);
}

int ctrl_coordinates(int x, int y) {
    if (first_city != NULL) {
        city* c = first_city;
        while (c->coordinate_x != x) {
            c = c -> next_city;
            if (c == NULL) {
                return (0);
            }
        }
        if (c -> coordinate_y != y) {
            return (0);
        } else {
            return (-1);
        }
    }
}

void create_route(char route_where_from, char route_where, int route_length) // functional
{
    g_route_ID++;
    int ok = 0;
    city* c = first_city;
    route* rr = NULL;

    while (c != NULL)
    {
        if (c -> name == route_where_from) 
        {
            route* r = new route();
            r -> length = route_length;
            r -> route_ID = g_route_ID;
            r -> next_route = NULL;
            r -> where = route_where;
            r -> where_from = route_where_from;
            r -> where_from_ID = find_city_ID(route_where_from);
            r -> where_ID = find_city_ID(route_where);
//            printf("Nova cesta - ID: %d, adresa: %d, z: %c, do: %c, delka: %d, dalsi: %d\n", (int) r, r ->route_ID, r->where_from, r->where, r->length, (int) r->next_route);
            if (c -> route_out == NULL) {
                c -> route_out = r;
//                printf("1.Zapsana cesta (%d) do route_out(%c) adresa(%d), next(%d)\n",r->route_ID, c->name, (int)r, (int)r->next_route);
            }
            else
            {
                rr = c -> route_out;
                while(rr -> next_route != NULL)
                {
                    rr = rr->next_route;
                }
                rr -> next_route = r;
//                printf("1.Zapsana cesta (%d) do cesty(%c - %d) adresa(%d), next(%d)\n",r->route_ID, c->name, (int)rr, (int)r, (int)r->next_route);
            }
            ok++;
        }
        if (c -> name == route_where)
        {
            route* r = new route();
            r -> length = route_length;
            r -> route_ID = g_route_ID;
            r -> next_route = NULL;
            r -> where = route_where;
            r -> where_from = route_where_from;
            r -> where_from_ID = find_city_ID(route_where_from);
            r -> where_ID = find_city_ID(route_where);
//            printf("Nova cesta - ID: %d, adresa: %d, z: %c, do: %c, delka: %d, dalsi: %d\n", (int) r, r ->route_ID, r->where_from, r->where, r->length, (int) r->next_route);
            if (c -> route_out == NULL)
            {
                c -> route_out = r;
//                printf("2.Zapsana cesta (%d) do route_out(%c) adresa(%d), next(%d)\n",r->route_ID, c->name, (int)r, (int)r->next_route);
            }
            else
            {
                rr = c -> route_out;
                while(rr ->next_route!= NULL)
                {
                    rr = rr->next_route;
                }
                rr -> next_route = r;
//                printf("2.Zapsana cesta (%d) do cesty(%c - %d) adresa(%d), next(%d)\n",r->route_ID, c->name, (int)rr, (int)r, (int)r->next_route);
            }
            ok++;
        }
        c = c -> next_city;
    }
    if (ok != 2){printf("Oou chyba - cesta nema jednu nebo obe destinace\n");}
}


void read_input() // functional
{
    int cnt;
    char c = '0';

    char ID_city;
    int c_x;
    int c_y;

    char route_where_from;
    char route_where;
    int route_length;

    scanf("%d", &cnt);

//    printf("Nacteno pocet mest %d\n",cnt);

    while((c != '\n') && (c != 13)){scanf("%c", &c);}

    for (int i = 0; i < cnt; i++)
    {
        scanf("%c",&ID_city);
        scanf("%d", &c_x);
        scanf("%d", &c_y);
//        printf("nacteno mesto - %c, %d, %d\n",ID_city,c_x,c_y);
        if (ctrl_coordinates(c_x, c_y) == -1) {
            printf("Pozor - zadavate misto na stejne souradnice - misto: %c, souradnice x: %d y: %d", ID_city, c_x, c_y);
        }
        create_city(ID_city, c_x, c_y);
//        printf("vytvoreno mesto - %c, %d, %d\n",ID_city,c_x,c_y);
        while((c != '\n') && (c != 13)){scanf("%c", &c);}
        scanf("%c", &c);
    }

    c = '0';

//    printf("dokonceno nacitani mest\n");
    
    scanf("%d", &cnt);

//    printf("Nacteno pocet cest %d\n",cnt);

    while((c != '\n') && (c != 13)){scanf("%c", &c);}

    for (int i = 0; i < cnt; i++)
    {
        scanf("%c", &route_where_from);
        scanf("%c", &c);
        scanf("%c", &route_where);
        scanf("%d", &route_length);
//        printf("nactena cesta: %c, %c, %d\n",route_where_from, route_where, route_length);
        if (route_length <= 0)
        {
            printf("Cesta z %c do %c delky %d nemuze existovat - nelze mit cestu nulove nebo zaporne delky...\n",route_where_from,route_where,route_length);
        }
        else
        {
            if (route_where == route_where_from){
                            printf("Pozor na zadani!! - Cesta z %c do %c delky %d vychazi a vede do stejneho mesta...\n",route_where_from,route_where,route_length);
            }
            create_route(route_where_from, route_where, route_length);
        }
//        printf("ulozena cesta: %c, %c, %d\n",route_where_from, route_where, route_length);
        while((c != '\n') && (c != 13)){scanf("%c", &c);}
    }
}

void add_item_of_queue(queue* q) //controled
{
//    printf("add_item_of_queue - start \n");
    queue* qq = actual;
    while((qq -> route_length < (q -> route_length)) && (qq -> next != NULL))
    {
        qq = qq -> next;
    }
    if ((qq -> next == NULL) && (qq->route_length < q->route_length))
    {
        q -> prev = qq;
        q -> next = NULL;
        qq -> next = q;
    }
    else
    {
//        printf("umistuji polozku na misto uvnitr fronty, q: %d, qq: %d, q->p: %d, qq->p: %d, a= %d\n", (int)q->route_length, (int)qq, (int)q->prev, (int)qq->prev, (int)actual);
        q -> next = qq;
        q -> prev = qq -> prev;
        qq -> prev -> next = q;
        qq -> prev = q;
    }
}

void delete_item_of_queue(queue* q) //controled
{
    if (q == actual)
    {
        actual = actual -> next;
        actual -> prev = NULL;
        delete(q);
    }
    else
    {
        if (q -> next == NULL)
        {
            q -> prev -> next = NULL;
            delete(q);
        }
        else
        {
            if (q->next == NULL) {
    }
        if (q->prev == NULL) {
    }
            q -> prev -> next = q -> next;
            q -> next -> prev = q -> prev;
            delete(q);
        }
    }
}

void modify_route_in(char to, route* r_in) // controled
{
    city* c = first_city;
    if (c == NULL) {err(3);}
    while(c -> city_ID != to)
    {
        if (c == NULL){err(3);}
        c = c -> next_city;
    }
    c -> route_in = r_in;
}

void search_new_routes() // controled
{
//    printf("Start searching new routes..\n");

    city* c = first_city;
    route* r = NULL;
    queue* q = actual;
    int to;
    int exists;
    city* cc = NULL;
/* Najde se mesto, ktere je na vrcholu fronty */
    while (actual -> city_ID != c -> city_ID)
    {
        if (c == NULL) {err(1);}
        c = c -> next_city;
    }
/* Mesto nalezeno, nyni je ulozeno v c(jeho adresa) */
    r = c -> route_out; // načtení první cesty z mesta
/* procházení postupně všech cet z města, které vedou do dalších měst - vytváření fronty k dalším něstům */
    while(r != NULL)
    {
        q = actual;
        if (q -> city_ID == r -> where_ID)
        {
//            printf("Mesto je where ID, takze jej prirazuju q->city_ID: %d, r->where: %d, r-> where_from: %d", q -> city_ID, r->where_ID, r->where_from_ID);
            to = r -> where_from_ID;
        }
        else
        {
//            printf("Mesto neni where ID, takze jej prirazuju q->city_ID: %d, r->where: %d, r-> where_from: %d", q -> city_ID, r->where_ID, r->where_from_ID);
            to = r -> where_ID;
        }
/* Pruchod cele fronty, jestli neni k danemu mestu jiz vytvorena polozka ve fronte  */
        exists = 0;
        while((q != NULL) && (exists != 2))
        {
            cc = first_city;
            if (cc == NULL) {err(2);}
/* Nalezení mesta, kam vede cesta r */
            while(cc -> city_ID != to)
            {
                if (cc == NULL){err(1);}
                cc = cc->next_city;
            }
/* test, jestli neni mesto uz uzavreno */
//            printf("test na uzavrene mesto - begin\n");
            if (cc->close == 1)
            {
//                printf("mesto je zavreno - %d\n",cc->city_ID);
                q = q -> next;
                exists = 2;
                continue;
            }
//            printf("test na uzavrene mesto - end %d\n",cc->close);
/*--------------------------------------*/
/* Kontrola, jestli neni vytvorena stejna polozka fronty, pokud ano, modikuje se a upravi se cela fronta */
            if (q -> city_ID == to)
            {
//                printf("polozka %d fronty existuje\n", q-> city_ID);
                if (q -> route_length > (actual -> route_length + r -> length))
                {
 //                   printf("polozka fronty potrbuje modifikaci \n");
                    delete_item_of_queue(q);
                    q = new queue();
                    q -> city_ID = to;
                    q -> route_length = (actual -> route_length + r -> length);
                    modify_route_in(to, r);                    
                    add_item_of_queue(q);
                }
                q = NULL;
                exists = 1;
                continue;
            }
            q = q -> next;
/*------------------------------------------------------------------------------------------------------ */
        }
        if (exists == 0)
        {
//            printf("vytvoreni nove polozky\n");
            q = NULL;
            q = new queue();
            q -> city_ID = to;
            q -> route_length = actual -> route_length + r -> length;
            if (r->length == 0){err(8);}
            modify_route_in(to, r);
            add_item_of_queue(q);
//            printf("dokonceno pridani polozky \n");
        }
        r = r->next_route;
    }
}
void close_city(int ID) // controled
{
    city* c = first_city;
    if (c == NULL){err(5);}
    while(c -> city_ID != ID)
    {
        if (c == NULL){err(5);}
        c = c->next_city;
    }
    c -> close = 1;
}

void search_usefull_routes() //contrled
{
    int iii = 0;
    actual -> city_ID = 1;
    actual -> next = NULL;
    actual -> prev = NULL;
    actual -> route_length = 0;
    while(actual != NULL)
    {
        iii++;
//        printf("Pruchod %d- hledam cesty..\n",iii);
        close_city(actual->city_ID);
        search_new_routes();

        if (actual->next == actual->prev)
        {
           delete(actual);
           actual = NULL;
           if (iii < g_city_ID) 
           {
               printf("Program dokoncil hledani, ale neprosel vsechna mista - zrejme do nejakeho mista nevede cesta!!\n");
               g_city_ID = -1;

           }
        }
        else
        {
                delete_item_of_queue(actual);
        }
    }
}


int main(int argc, char** argv) //controled
{
    printf("Vitej v programu starosta - semestralni prace z TIN, vytvoril Michal Zima \n\n\n");
    printf("Zadej potrebne parametry ve tvaru - \n 1.radek - n = pocet mest \nnasleduje n radku s nazev_mesta souradnice_X souradnice_Y\nradek s m = pocet cest\nnasleduje m radku s odkud_vede_cesta(jmeno mesta) kam_vede_cesta(jmeno mesta) delka cesty\n");
    read_input(); // postupne nacitani vsech radku vlaken
    print();
    printf("Hotovo - nacteno vporadku!!\n");
    search_usefull_routes();
    print_usefull();
    if (g_city_ID == -1){
        printf("\nDoslo k chybe - cesty nevedou do vsech casti mesta!!\n\n");
    }
    return (EXIT_SUCCESS);
}
